【操作系统实验】进程调度（Linux环境下）

【实验目的】

实验目的：

（1）通过编写程序实现进程或作业先来先服务、高优先权、按时间片轮转调度算法，使 学生进一步掌握进程调度的概念和算法，加深对处理机分配的理解。 （2）了解进程（线程）的调度机制。 （3）学习使用进程（线程）调度算法，掌握相应的与调度有关的 API 函数。

实验要求： （1）经调试后程序能够正常运行。 （2）采用多进程或多线程方式运行，体现了进程或作业先来先服务、高优先权、按时间片轮转，高相应比优先调度算法。 （3）程序界面美观。

【实验内容】

进程调度相关算法：实现先来先服务、短作业优先、按时间片轮转、按优先级、高响应比优先。

【实验环境】（含主要设计设备、器材、软件等） Pc电脑一台

【实验步骤、过程】（含原理图、流程图、关键代码，或实验过程中的记录、数据等）

1.FCFS（先来先服务）和SJF（短作业优先）调度算法   先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。   流程图如下所示：

            图1 FCFS算法流程图

代码如下：

(1)FCFS部分

            图2 FCFS代码实现

(2)SFJ部分

            图3 SFJ代码实现

执行结果如下：

(1)FCFS部分   先选择FCFS,设置四个进程；到达时间为分别为530、540、480、590，运行时间分别为50、10、120、20。即可得到如下结果：

            图4 FCFS运行结果

(2)SFJ部分   先选择SFJ,设置四个进程；到达时间为分别为530、540、480、590，运行时间分别为50、10、120、20。即可得到如下结果：

            图5 SFJ运行结果

2.时间片轮转（RR）调度算法   时间片轮转（RR）调度算法是专门为分时系统设计的。它类似于 FCFS调度，但是增加了抢占以切换进程。该算法中，将一个较小时间单元定义为时间量或时间片，时间片的大小通常为 10~100ms。就绪队列作为循环队列，CPU 调度程序循环整个就绪队列，为每个进程分配不超过一个时间片的 CPU。为了实现 RR 调度，我们再次将就绪队列视为进程的 FIFO 队列。新进程添加到就绪队列的尾部。CPU 调度程序从就绪队列中选择第一个进程，将定时器设置在一个时间片后中断，最后分派这个进程。   流程图如下所示：

            图6 RR流程图

代码如下：

            图7 RR代码实现

执行结果如下：   共设置四个进程，这四个进程所需时间分别为2、5、1、6

            图8 RR执行结果

  这里是用4个进程，分别需要2、5、1、6个单位时间运行，由运行过程可以看到，在一个时间片范围内，会选择一个进程执行，然后切换到下一个进程，所以说这种调度方式，是绝对公平的。虽说在某些情况下，带权周转时间可能不如其他的调度算法，但是，在实现人机交互上，这种算法是非常实用的。

3.高优先级调度算法   该算法用于作业调度时，系统从后备作业队列中选择若干个优先级最高的，且系统能满足资源要求的作业装入内存运行。当该算法用于进程调度时，将把处理机分配给就绪进程队列中优先级最高的进程。高优先级调度算法分为抢占的高优先级调度算法和非抢占的高优先级调度算法。非抢占式优先级算法，这种调度方式下，系统一旦把处理机分配给就绪队列中优先级最高的进程后，该进程就能一直执行下去，直至完成；或因等待某事件的发生使该进程不得不放弃处理机时，系统才能将处理机分配给另一个优先级高的就绪进程。抢占式优先级调度算法，在这种调度方式下，进程调度程序把处理机分配给当时优先级最高的就绪进程，使之执行。一旦出现了另一个优先级更高的就绪进程时，进程调度程序就停止正在执行的进程，将处理机分配给新出现的优先级最高的就绪进程。   设置进程控制块结构体，以链表的形式构成进程组，包括进程名、需求时间、优先级、状态等信息。在运行时，选取优先级最高的进程执行，之后将此进程优先级降低，然后对所有进程排序，再重复此过程，直到所有进程执行完毕。   流程图如下;

            图9 Priority流程图

代码如下：

            图10 Priority代码实现

执行结果如下：   四个进程的优先级分别为5、1、2、4   每个进程执行一个时间单位后优先级自动下降1

            图11 Priority执行结果

  这里采用的是比较典型的优先级调度算法，每次被执行的进程，它的优先级都会降低1，每回再选取优先级最高的进程来指向。   而此处输入的是4个进程：进程a，需求时间5，优先级5；进程b，需求时间2，优先级1；进程c，需求时间10，优先级2；进程d，需求时间12，优先级4.它们会按上图所示的顺序，逐个地完成执行。而从中可以看出，优先级调度算法，比较适合于有紧急作业的用户，而在其它方面并不占优。

4.高响应比调度算法   该算法实际上是一种动态优先调度算法，它以相应比作为作业或进程的动态优先权，其目的是既照顾短作业，又考虑到作业的等待时间，使长作业不会长期等待；但每次调度前，都要进行响应比计算，会增加系统开销。响应比 = 相应时间 / 要求服务时间 = 等待时间 + 要求服务时间 / 要求服务时间。

            图12 HRRF流程图

代码实现如下：

            图13 HRRF代码实现

执行结果如下：   分别设置了四个进程，p1的开始时间为2，运行时间为6；p2的开始时间为4，运行时间为12；p3的开始时间为1，运行时间为2；p4的开始时间为3，运行时间为10。各自的带权周转时间与最后完成调度后的平均周转时间与平均带权周转时间如图14所示。

            图14 HRRF执行结果

【实验结果或总结】（对实验结果进行相应分析，或总结实验的心得体会，并提出实验的改进意见）

  此次实验，是关于进程调度的，而这次一共实现了4种调度方法：FCFS（先来先服务）、SJF（短作业优先）、RR（按时间片调度）、Priority（按动态优先级抢占调度）。   通过用一些例子来运行这些算法，对这几种算法有了更深一步的理解。FCFS算法简单而利于实现，但是不便于IO处理和作业调度，适用于辅助算法，而不做为专门算法；SJF算法利于短作业，可以有效地缩短作业平均周转时间，提高系统吞吐量，但是并不利于长作业和紧急作业；RR算法也是简单易行，而且平均响应时间短，但是不适于处理紧急作业；Priority算法，由于这里采用的是动态优先级，所以既可以避免低优先级的进程长期处于饥饿状态，又可以防止一个长作业长期垄断处理机，整体算法适用于处理紧急作业。   不同调度算法在代码思路和代码实现方面有较大的差异，综合考虑到数据结构和算法；先来先服务算法和短作业优先算法可以用栈来实现；按优先级调度算法可以用优先级队列来实现等等。通过这次实验懂得了理论和代码的差距，虽然理论课听懂了但实践起来也有些差距。通过这次实验更加深入的理解了进程调度的各个算法的实现，思想及适合的情况。   最后感谢倪福川老师的指导以及所有向我提供帮助的同学们！